package num210;

import java.util.*;

/**
 * @author : DuJiabao
 * @Project : sword-finger-offer
 * @Time : 2021/5/9 23:18
 * @Desc :
 */
public class Solution {
  public int[] findOrder(int numCourses, int[][] prerequisites) {
    if (numCourses == 0) return new int[0]; // 没有课就别进来了
    List<List<Integer>> graph = new ArrayList<>();
    int[] inNums = new int[numCourses];  // 每节课需要的先修课程个数，也就是出度数
    Arrays.fill(inNums, 0);
    for (int i = 0; i < numCourses; i++) {
      graph.add(new LinkedList<>());
    }
    for (int[] prerequisite : prerequisites) {
      int preId = prerequisite[1];
      int postId = prerequisite[0];
      graph.get(preId).add(postId); // 表示后修课程需要先修课程
      inNums[postId]++;
    }

    ArrayList<Integer> res = new ArrayList<>();
    bfs(inNums, res, graph);
    if (res.size() != numCourses) return new int[0];
    int[] result = new int[numCourses];
    for (int i = 0; i < res.size(); i++) {
      result[i] = res.get(i);
    }
    return result;
  }

  public void bfs(int[] inNums, List<Integer> res, List<List<Integer>> graph) {
    // 进来，首先更新队列，所有入度为0，也就是所有不需要依赖的课程，先入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < inNums.length; i++) {
      if (inNums[i] == 0) queue.offer(i);
    }
    // 如果发现队列已经为空，那就不用玩了
    if (queue.isEmpty()) return;
    // 如果不为空，那就把队列所有成员上一遍
    while (!queue.isEmpty()) {
      Integer classId = queue.poll();  // 成员取出来
      //System.out.println(classId + " -> ");
      res.add(classId); // 上完的课放进结果里面
      inNums[classId] = -1; // 当前课已经被修完了，修改一下标志，避免又去修了
      for (Integer nextId : graph.get(classId)) {  // 更新一下依赖于这个课程的课程，给他们减一，表示又少了一门负担
        inNums[nextId]--;
      }
    }
    bfs(inNums, res, graph); // 继续递归
  }


  public static void main(String[] args) {
    int[][] classes = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
    //int[][] classes = {{1, 0}};
    int[] res = new Solution().findOrder(4, classes);
    System.out.println(Arrays.toString(res));
  }

}
